﻿#ifndef _DATA_STRUCTURE_H_
#define _DATA_STRUCTURE_H_ 1


/************************************************************************/
/* xinglong gao  copied right @haierubic                                */
/************************************************************************/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>


#include "BlockQueue.h"
#include "BlockShaper.h"
#include "ByteBuffer.h"


using namespace std;
//forward declarations
struct ForwardLink;
class FloatMatrix;
class StructOperations;
class PriorityQueue;
class DecisionTree;
class Histogram;
class MutualNode;



void BlockQueueTest();
void BlockShaperTest();
void ByteBufferTest();

void BasicDataStructure();





#define TEST_ASSERT(var) do \
{\
if(var == 0) std::cout << "ERROR\n";\
} while (0);


//FORWAR CLARATIONS
class SortVector;
class Histogram;
class ProgramOpts;





enum class ComponentType
{

	kComponentGRU = 0x00001,
	kComponentBN = 0x00002,
	kComponentCNN,
	kInput,
	kOutput,
	kComponentUNK

};





#ifdef _WIN32
typedef int int32;
#elif (defined _WIN64)
typedef long long int int64;
#endif


class SmallNode {
public:
	SmallNode() :i(0), counter_(0) ,k(0){};
	virtual ~SmallNode() {};
	const int Returni() const {
		return i;
	}

	void test2() {

	}
public:
	mutable int32 counter_;
	const int i;
	int k;
};
void TestMutale(const SmallNode* in);


class SortVector
{
public:
	SortVector() :data_len_(0) {}
	SortVector(int vec_len) :data_len_(vec_len)
	{
		data_.reserve(vec_len);
		internal_data_.reserve(vec_len);
	}

	virtual ~SortVector()
	{
	}

	void InitDataFromText(const char* digital_file);

	inline std::vector<int>& Array() {
		return data_;
	}

	void MergeSort(std::vector<int>& chaos_array) {
		if (data_len_ == 0) {
			return;
		}
		MergeSortImpliment(0, data_len_ - 1);
	};
	void QuickSortMain() {
		if (data_len_ == 0) {
			return;
		}
		PrintInternalArray();
		//////////////////////////////////////////////////////////////////////////

		QuickSortImpli(0, data_len_ - 1);
		//////////////////////////////////////////////////////////////////////////
		PrintInternalArray();
	};
	virtual void InsertSort() {
		//down order for a input int array
		if (data_len_ == 0) {
			return;
		}
		PrintInternalArray();
		for (int i = 1; i < data_len_; i++)
		{
			for (int j = i; j > 0; j--)
			{
				if (data_[j] < data_[j - 1]) {
					SwapInts(data_[j], data_[j - 1]);
				}
			}
		}
		PrintInternalArray();
	};


	void PrintInternalArray();
	inline void ReInitData() {
		data_.clear();
		data_.resize(internal_data_.size());
		std::copy(internal_data_.begin(), internal_data_.end(), data_.begin());
	}
protected:

	void QuickSortImpli(int start_index, int end_index) {
		//we sort this vector in original location
		int key_index = (start_index + end_index) / 2;
		for (size_t i = start_index; i < key_index; i++)
		{
			if (data_[i] < data_[i + key_index]) {
				SwapInts(data_[i], data_[i + key_index]);
			}
		}
		QuickSortImpli(start_index, key_index);
		QuickSortImpli(key_index, end_index);

	}
	void SwapInts(int& a, int& b) {
		int temp = a;
		a = b;
		b = temp;
	}

	void MergeSortImpliment(int start_index, int end_index) {
		//we sort this vector in original location
		;

	}
private:
	std::vector<int> data_;
	std::vector<int> internal_data_;
	int data_len_;

};


typedef struct _Token
{
	_Token() {};
	_Token(float total_cost, float ac_coust, float graph_cost) {
		total_weight_ = total_cost;
		ac_weight_ = ac_coust;
		lm_weight_ = graph_cost;
	};


	//basic data storage
	float total_weight_;
	float ac_weight_;
	float lm_weight_;
	ForwardLink* forward_links;


}Token;



typedef struct ForwardLink
{
	Token* next_token;
	Token* best_preceeding_token_;
	ForwardLink* next_;
	float ac_weight_;
	float lm_weight_;
	float total_weight_;
	ForwardLink(float ac_cost, float lm_cost, float total_cost,
		ForwardLink* next_link, Token* n_token) {
		next_token = n_token;
		best_preceeding_token_ = nullptr;
		next_ = next_link;
		ac_weight_ = ac_cost;
		lm_weight_ = lm_cost;
		total_weight_ = total_cost;
	}
};


typedef struct MutualNode
{
	int value_;
	DecisionTree* classified_tree_;
	MutualNode* left;
	MutualNode* right;
	MutualNode() {
		value_ = 0;
		classified_tree_ = nullptr;
		left = nullptr;
		right = nullptr;
	}
};





class FloatMatrix
{
public:
	FloatMatrix()
	{
	}
	FloatMatrix(int row, int col, int stride) :row_num_(row),
		col_num_(row), stride_(stride) {
		data_ = new float[row_num_*stride_];
	}
	FloatMatrix(const FloatMatrix& other) {
		if (&other == this) {
			return;
		}
		this->row_num_ = other.row_num_;
		this->row_num_ = other.col_num_;
		this->stride_ = other.stride_;
		memcpy(static_cast<float*>(this->data_), static_cast<float*>(other.data_), other.row_num_*other.col_num_);
	}
	FloatMatrix& CopyFromOther(const FloatMatrix& other) {
		if (&other == this) {
			return *this;
		}
		this->row_num_ = other.row_num_;
		this->row_num_ = other.col_num_;
		this->stride_ = other.stride_;
		memcpy(static_cast<float*>(this->data_), static_cast<float*>(other.data_), other.row_num_*other.col_num_);
		return *this;
	}


	virtual ~FloatMatrix()
	{
	}

	float operator()(int row_index, int col_index) {
		if (row_index >= row_num_ || col_index >= col_num_) {
			std::cerr << "ERROR\n";
			exit(-1);
		}
		return *(data_ + row_index*stride_ + col_index);
	}

	int RowNum() const {
		return row_num_;
	}

	int ColNum() const {
		return col_num_;
	}

	int Stride() const {
		return stride_;
	}

private:
	float* data_;
	int row_num_;
	int col_num_;
	int stride_;
};



class CircleQueue
{
public:
	CircleQueue() {};
	virtual ~CircleQueue() {
		if (storage_)
		{
			delete[] storage_;
			storage_ = nullptr;
		}
	};
	void PushBackSpecifiedNumberBlocks(const char* src, int specified_num) {

		if (strlen(src) != specified_num*block_size_)
		{
			//error
			return;
		}
		int tail_after_copied = (queue_head_ + specified_num*block_size_) % queue_len_;
		while (tail_after_copied > queue_tail_)
		{
			//queue can not store the new data
			Resize();
		}
	
		if (IsNewBlockNeedSplit(specified_num))
		{

		}
		else
		{

		}
	}

	void PushBackRandomLenghth(const char* src, int src_len) {
	
	
	}
	char* GetSpecifiedNumberBlocks(int specified_num) {
		
	}

	inline bool Isfull() {
	
	}
	inline bool Isempty() {
	
	}



protected:

	void Resize(int new_size = 1024) {
		char* new_storage_ = new char[storage_len_ + new_size];
		if (new_storage_ == nullptr)
		{
			return;
		}
		if (queue_tail_ < queue_head_) //circle right location
		{
			memcpy(static_cast<char*>(new_storage_+ queue_head_), static_cast<char*>(storage_+ queue_head_), storage_len_-queue_head_);
			memcpy(static_cast<char*>(new_storage_ + storage_len_), static_cast<char*>(storage_), queue_tail_);
			delete[] storage_;
			storage_ = new_storage_;
		}
		else //normal case : header always less than tail location
		{
			memcpy(static_cast<char*>(new_storage_ + queue_head_), static_cast<char*>(storage_), queue_len_);
		}
		storage_len_ += new_size;
	};

	bool IsNewBlockNeedSplit(int new_block_num) {
		int new_queue_head = queue_head_ + new_block_num*block_size_;
		if (new_queue_head > storage_len_)
		{
			return true;
		}
		return false;
	}
private:
	char* storage_;
	int storage_len_;
	static const int block_size_ = 8;
	int queue_head_;
	int queue_tail_;
	int queue_len_;
};


class TokenHeap
{
public:
	TokenHeap():heap_(0), heap_head_(0),heap_tail_(0)
	{
	}

	~TokenHeap()
	{
		if (heap_)
		{
			delete[] heap_; heap_ = nullptr;
		}
	}

private:
	char* heap_;
	char* heap_head_;
	char* heap_tail_;
	long long heap_len_;
	const long long heap_block_size_ = 1024;

};



class DoubleTrie
{
public:
	DoubleTrie(int tree_size):storage_size_(tree_size)
	{
		
	}

	~DoubleTrie()
	{
	}

public:
	void Insert() {
	}

	bool Search(char* s) {
		int rt = 0;
		for (int i = 0; s[i]; i++)
		{
			int x = s[i] - 'a';
			if (trie[rt][x] == 0)return false;//以rt为头结点的x字母不存在，返回0 
			rt = trie[rt][x];//为查询下个字母做准备 
		}
		return true;
		//查询整个单词时，应该return isw[rt] 
	}

private:
	char* storage_;
	char** storage_next_;
	int storage_size_;
	char trie[1024][1024];

};

// define for bidirectional list and binary tree [4/16/2018 lenovo]
class DecisionTree
{
public:
	DecisionTree():tree_storage_(nullptr), leaves_(0), root_index_(0)
	{
	}

	virtual ~DecisionTree()
	{
	}

	void Init() {};
	void ConstructTree() {};
	void DrawTree() {};
private:
	char* tree_storage_; //we use char[] to store this binary tree
	int leaves_;
	int root_index_;
};





template <typename Elem>
class FreeSingleObj
{
public:
	FreeSingleObj()
	{
	}

	~FreeSingleObj()
	{
	}
	Elem * operator()(Elem* obj) {
		delete obj;
		obj = nullptr;
		return obj;
	}
private:

};


class PriorityQueue
{
public:
	PriorityQueue() :queue_root_(nullptr), queue_size_(0)
	{
	}

	~PriorityQueue()
	{
	}

private:
	MutualNode* queue_root_;
	int queue_size_;
};





class Histogram
{
public:

	Histogram() :data_(nullptr), len_data_(0), hist_size_(0) {}
	Histogram(int hist_num) :data_(0), len_data_(0), hist_size_(hist_num),note_(0)
	{
	}

	virtual ~Histogram()
	{
	}
	void InitFromFile(const char* data_file);
	void Spill2Histogram() {
		ComputeHistogram();
	}

	
public:
	int note_;

protected:

	float ComputeHistogram() {

		return 0.0;
	}
	void FriendTest(StructOperations& so) {
		//std::cout << so.free_node_num_ << std::endl;
	}
private:
	int * data_;
	int len_data_;
	int hist_size_;

};



class StructOperations
{
	friend class Histogram;
public:
	StructOperations():list_head_(nullptr),
		tree_root_(nullptr), free_head_(nullptr),tail_(nullptr),free_node_num_(1024),
		is_binary_search_(false)
	{
	}

	virtual ~StructOperations()
	{
		FreeList();
		FreeTree();
	}

	void InitList(const char* list_cfg);
	void InitTree(const char* tree_cfg);
	MutualNode* InitTreeRecursive(istream& is, std::queue<MutualNode*>& temp_leaves);
	void BinaryTree2BirectionList();
	void BirectionList2BinaryTree();

	void SortListTop2down();
	void DrawTree();


	MutualNode* ConvertToBinarySearchTree();

	MutualNode* Search(MutualNode* bin_tree_root, int key) const {
		if (bin_tree_root == nullptr){
			return nullptr;
		}
		MutualNode* result_node = bin_tree_root;
		while (result_node != nullptr && result_node->value_ != key)
		{
			if (result_node->value_ <= key){
				result_node = result_node->right;
			}
			else
			{
				result_node = result_node->left;
			}
		}
		return result_node;

	}

	void InsertElementToBinTree(int new_value) {
	
	
	}

	void DeleteElementFromBinTree(int first_find_result) {
		// there are may some elements with same value,  [4/29/2018 gaoxinglong]
		//so we only delete the first one !
	}

	bool IsBinarySearch() const {
		return is_binary_search_;
	}
	

	void SwapPointer(MutualNode*& left, MutualNode*& right) {
		if (left == right) {
			return;
		}
		MutualNode* temp = left;
		left = right;
		right = temp;
	}


	void SwapAddrs(MutualNode** left, MutualNode** right) {
		if (left == right) {
			return;
		}
		MutualNode** temp = left;
		*left = *right;
		*right = *temp;

	}

	void FindMin(int* in_data, int len) {
		if (! in_data || len == 0){
			return;
		}
		return;
	}

	void OnlyTestFriendMember(Histogram& hist) {
		std::cout << hist.note_ << std::endl;
	}

	void BirectionList2CircleList() {}


protected:
	void SwapInts(int& a, int& b) {
		int temp = a;
		a = b;
		b = temp;
	}
	
	void SwapMuturalNodes(MutualNode* nodea, MutualNode* nodeb) {
		if (nodea == nodea){
			return;
		}

		SwapInts(nodea->value_, nodeb->value_);
		SwapPointer(nodea->left, nodeb->left);
		SwapPointer(nodea->right, nodeb->right);

	}

	bool EatWs(std::istream& is) {
		std::string next_token;
		char next_char = ' ';
		while ((next_char = is.peek()) == ' ' || (next_char = is.peek()) == '\n' ||
			(next_char = is.peek()) == '\r')
		{
			is >> std::ws;
		}
		if (is.eof()){
			return true;
		}
		return false;
	}

	MutualNode* Resize() {
		if (free_head_==nullptr)
		{
			MutualNode* new_pool = ResizeMemoryPool();
			free_head_->right = new_pool;
			new_pool->left = free_head_;
		} else {
			

		}
	}

	void TraversalDFS(MutualNode* tree_root) {
		if (tree_root == nullptr){
			return;
		}
		/////////////////////   Here we define core operations for the //////////////////
		/////////////////////  current tree node, such as tree_root node  ///////////////
		std::cout << tree_root->value_ << std::endl; // we first print the value of current node



		///////////////////////Core operation definitions ending //////////////////////////////
		if (tree_root->left){
			TraversalDFS(tree_root->left);
		}
		if (tree_root->right){
			TraversalDFS(tree_root->right);
		}
	};


	MutualNode* DelMutualNode(MutualNode* delelted_node) {
		delelted_node->right = free_head_;
		delelted_node->left = nullptr;
		free_head_->left = delelted_node;
		free_head_ = delelted_node;
		free_node_num_++;
		return free_head_;
	};


	MutualNode* NewMutualNode() {
		if (free_head_){
			MutualNode* ans = free_head_;
			free_head_ = free_head_->right;
			ans->left = nullptr;
			ans->right = nullptr;
			free_node_num_--;
			return ans;
		}
		else
		{
			ResizeMemoryPool();
			MutualNode* ans = NewMutualNode();
			return ans;

		}

	}
	MutualNode* ResizeMemoryPool() {
		if (free_head_ == nullptr){
			//all elements have been used
			MutualNode* new_pool = new MutualNode[pool_size_];
			MutualNode* next = &free_head_[1];
			for (int i = 1; i < pool_size_; i++)
			{
				new_pool[i - 1].right = &new_pool[i];
				new_pool[i].left = &new_pool[i - 1];
				if (i == 1)
				{
					new_pool[i - 1].left = nullptr;
				}
				if (i == pool_size_ - 1)
				{
					new_pool[i].right = nullptr;
				}
			}
			free_head_ = new_pool;
			free_node_num_ = pool_size_;
			return new_pool;
		}
		else
		{
			//there are still some elements which are not allocated

			MutualNode* new_pool = new MutualNode[pool_size_];
			MutualNode* next = &free_head_[1];
			for (int i = 1; i < pool_size_; i++)
			{
				new_pool[i - 1].right = &new_pool[i];
				new_pool[i].left = &new_pool[i - 1];
				if (i == 1)
				{
					new_pool[i - 1].left = nullptr;
				}
				if (i == pool_size_ - 1)
				{
					new_pool[i].right = nullptr;
				}
			}
			tail_ = free_head_;
			MutualNode* curr_elem = free_head_;
			while (tail_)
			{
				curr_elem = tail_;
				tail_ = tail_->right;
			}
			tail_->right = new_pool;
			new_pool->left = tail_;
			free_node_num_ += pool_size_;
			return free_head_;
		}
		

	}
	

	void FreeList() {
		MutualNode* e = list_head_, *next_e = nullptr;
		while (e != nullptr)
		{
			next_e = e->right;
			delete e;
			e = next_e;
		}
	}
	void FreeTree() {

		//processing the left sub tree

		//processing the right sub tree

		//processing the root node

	}
private:
	MutualNode* list_head_;
	MutualNode* tree_root_;
	MutualNode* free_head_;
	MutualNode* tail_;
	int free_node_num_;
	static const int pool_size_ = 1024;
	bool is_binary_search_;
};






class ComponentBase
{
public:
	ComponentBase(int in_dim, int out_dim) {
	};
	virtual ~ComponentBase() {
	};

	// all of belower_node_back_time_ are interfaces of the next inherent ed class definitions [4/11/2018 lenovo]
	virtual bool InitFromConfig(const char* filename) {
		return true;
	};

	//3 main interfaces for this component
	virtual void ForwardCompute(FloatMatrix*prev_layer_in = nullptr,
		FloatMatrix* this_layer_out = nullptr) {};

	virtual void BackwardCompute(FloatMatrix*higher_layer_in = nullptr,
		FloatMatrix* lower_node_back_time_er_layer_out = nullptr) {};

	virtual void ApplyGradient(FloatMatrix*prev_layer_in = nullptr,
		FloatMatrix* this_layer_out = nullptr) {};


	virtual void BackPropCompute() {};
	virtual void ApplyGradient() {};

	virtual ComponentType Type() const {
		return ComponentType::kComponentUNK;
	}


	// some info which are not relevant with concise object
	static const int _obj_num = 0;



private:

};






class BatchNormComponent :public ComponentBase
{
public:
	BatchNormComponent(int _in_dim, int _out_dim) :ComponentBase(_in_dim, _out_dim),
		sigma_(0)
	{
	}

	~BatchNormComponent()
	{
		ComponentBase::~ComponentBase();
	}
	virtual bool InitFromConfig(const char* filename) {
		std::cout << "init at bn\n";
		return false;
	};
	virtual void ForwardCompute(FloatMatrix*prev_layer_in = nullptr,
		FloatMatrix* this_layer_out = nullptr) {};

	virtual void BackwardCompute(FloatMatrix*higher_layer_in = nullptr,
		FloatMatrix* lower_node_back_time_er_layer_out = nullptr) {};

	virtual void ApplyGradient(FloatMatrix*prev_layer_in = nullptr,
		FloatMatrix* this_layer_out = nullptr) {};


	ComponentType Type() const {
		return ComponentType::kComponentBN;
	}
private:

	int emisilon_;
	int sigma_;

};


class GruComponent : public ComponentBase
{
public:
	GruComponent(int _in_dim, int _out_dim) :ComponentBase(_in_dim, _out_dim),
		current_delta_error_(nullptr),
		current_gradient_(nullptr), current_input_(nullptr),
		current_output_(nullptr) {

	}
	~GruComponent() {
		ComponentBase::~ComponentBase();
	};

	virtual bool InitFromConfig(const char* filename) {
		return false;
	};
	virtual void ForwardCompute(FloatMatrix*prev_layer_in = nullptr,
		FloatMatrix* this_layer_out = nullptr) {};

	virtual void BackwardCompute(FloatMatrix*higher_layer_in = nullptr,
		FloatMatrix* lower_node_back_time_er_layer_out = nullptr) {};

	virtual void ApplyGradient(FloatMatrix*prev_layer_in = nullptr,
		FloatMatrix* this_layer_out = nullptr) {};


	ComponentType Type() const {
		return ComponentType::kComponentGRU;
	}



private:

	FloatMatrix* current_input_;
	FloatMatrix* current_output_;
	FloatMatrix* current_delta_error_;
	FloatMatrix* current_gradient_;
	//////////////////////////////////////////////////////////////////////////

	FloatMatrix* w_rx_;
	FloatMatrix* w_rh_;
	FloatMatrix* w_zx_;
	FloatMatrix* w_zh_;
	FloatMatrix* w_hh_;
	FloatMatrix* w_hx_;

};





class Conv1DComponent :public ComponentBase
{
public:
	Conv1DComponent(int _in_dim, int _out_dim) :ComponentBase(_in_dim, _out_dim),
		pool_size_(3), pool_step_(1), pool_stride_(128)
	{
		weights_.resize(0);
		bias_.resize(0);
	}

	virtual ~Conv1DComponent()
	{
		ComponentBase::~ComponentBase();
	}

	void ForwardCompute(FloatMatrix*prev_layer_in = nullptr,
		FloatMatrix* this_layer_out = nullptr) {
		;
	}

	void BackProp() {
		;
	}

	ComponentType Type() const {
		return ComponentType::kComponentCNN;
	}

private:
	std::vector<std::vector<float> > weights_;
	std::vector<float> bias_;
	int pool_step_;
	int pool_size_;
	int pool_stride_;
	int in_dim_;
	int out_dim_;

};


// Here we should define some algorithms about mathematic [4/16/2018 lenovo]

class MathAlorithms
{
public:
	MathAlorithms() :current_component_(nullptr)
	{
		componets_.clear();
	}

	~MathAlorithms()
	{
	}

	void Lbfgs_optimization() {};

	void Gradientdescent() {};

	void RnnTrain() {
		GruRnnTrain();

	}

protected:
	////////////////For gated recurrent unit //////////////////

	void GruNnetInit(const char* nnetwork_config);

	void GruRnnTrain();

	void GruRnnForward(FloatMatrix* in);

	void GruRnnBackward(FloatMatrix* in);

	void GruRnnApplyGradient() {};

private:

	void VerifyNextToken(istream& is, const char* expected_token) {
		is >> std::ws;
		bool read_bracket;
		if (static_cast<char>(is.peek()) == '<') {
			read_bracket = true;
			is.get();
		}
		int ans = is.peek();
		if (read_bracket) {
			std::string next_token;
			is >> next_token;
			if (next_token.compare(expected_token)) {
				exit(-1);
			}
		}
		is.get();
	}

	void ReadBasicType(istream & is, double* d) {
		is >> *d;
		is.get();
	}


	ComponentType StringToComponentType(const char* comp_head_string) {
		ComponentType type;
		std::string header_note = comp_head_string;
		if (header_note == "<input>") {
			type = ComponentType::kInput;
		}
		else if (header_note == "<GRUComponent>")
		{
			type = ComponentType::kComponentGRU;
			return type;
		}
		else if (header_note == "<output>") {
			type = ComponentType::kOutput;
			return type;
		}
		else
		{
			std::cout << "Unknown string type.\n";
			exit(-1);
		}
		return type;
	};

private:
	static const std::string gru_network_config;
	std::string gru_nnetwork_cfg_lines;
	std::vector<ComponentBase* >componets_;
	GruComponent* current_component_;



};






class GreedySolution
{
public:
	GreedySolution() :wfst_root_(0)
	{
	}

	virtual ~GreedySolution()
	{
	}

private:
	MutualNode* wfst_root_;
};


struct ListNode
{
	int val;
	ListNode* next;
	ListNode(int x) :val(x), next(nullptr) {}
};



void DSTest(const char* init_cfg);
void LeetCodeLearning(const char* usage);
void GraphAlgrithms();
// Leetcode4
void FindMedianTest();
int FindMedianofTwoUnSortedArrays(std::vector<int>& array_a, std::vector<int>& array_b);
int FindKthofTwoUnSortedArrays(std::vector<int>& array_a, std::vector<int>& array_b, int kth);
int FindKthSpecial(std::vector<int>& array_a, std::vector<int>& array_b, int kth);
//Leetcode3
std::string LongestSubStrwithoutRepeatedChars(std::string s);
int lengthOfLongestSubstring(const char* s);
//Leetcode1
std::vector<int> twoSum(vector<int>& nums, int target);
//Leetcode2
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2);
// Leetcode 16
int threeSumClosest(vector<int>& nums, int target);
int kSumClosest(vector<int>& nums, int k, int target);
// Leetcode
int largestRectangleInHistogram();
void SortTest(const char* digital_file);
void BasicTest(ComponentBase* component);
//
void RightMove();

bool EatWs(std::istream& is);

#endif